package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _11_判断t1树中是否有与t2树拓扑结构完全相同的子树_serialize {

    public static boolean isSubTree(TreeNode t1, TreeNode t2) {

        return serialize(t1).contains(serialize(t2));
    }


    public static String  serialize(TreeNode t) {

        StringBuilder sb = new StringBuilder();
        doSerialize(t,sb);
        return sb.toString();
    }

    public static void doSerialize(TreeNode t,StringBuilder sb) {

        if (t == null) {

            sb.append("*").append("#");
            return;
        }

        sb.append(t.val).append("#");
        doSerialize(t.left,sb);
        doSerialize(t.right,sb);
    }

    public static void main(String[] args) {

        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.left.left = new TreeNode(4);
        t1.left.left.left = new TreeNode(8);
        t1.left.left.right = new TreeNode(9);
        t1.left.right = new TreeNode(5);
        t1.left.right.left = new TreeNode(10);
        t1.right = new TreeNode(3);
        t1.right.left = new TreeNode(6);
        t1.right.right = new TreeNode(7);

        TreeNode t2 = new TreeNode(2);
        t2.left = new TreeNode(4);
        t2.left.left = new TreeNode(8);
        t2.right = new TreeNode(5);

//        TreeNode t2 = new TreeNode(3);
//        t2.left = new TreeNode(6);
//        t2.right = new TreeNode(7);

        boolean result = isSubTree(t1, t2);
        System.out.println(result);

    }
}

